public class Sort {
    //冒泡排序：
    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //稳定性：稳定
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                }
            }
        }
    }

    private static void swap(int[] array, int j, int i) {
        int tmp = array[j + 1];
        array[j + 1] = array[j];
        array[j] = tmp;
    }


    //计数排序(桶排序)：
    //无需比较大小


    public static void countSort(int[] array){
        //首先先创建一个新数组，作为桶
        int[] bucket = new int[array.length];
        //遍历一遍原数组，将数据放入
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        //放完之后，打印
        for (int i = 0; i < bucket.length; i++) {
            while(bucket[i] != 0){
                System.out.print( i + " ");
                bucket[i]--;
            }
        }
    }

    //归并排序
    //分治法：分而治之
    //时间复杂度：O(NlogN)
    //空间复杂度：O(logN) -> (树的高度)
    //稳定性：稳定

    public static void mergeSort(int[] array){
        merge(array,0,array.length - 1);
    }

    private static void merge(int[] array, int left, int right) {
        if(left >= right){
            return ;
        }
        //分解
        int mid = (left + right) / 2;
        merge(array,left,mid);
        merge(array,mid + 1,right);
        //合并
        combine(array,left,right,mid);
    }

    private static void combine(int[] array, int left, int right, int mid) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int k = 0;
        int[] tmp = new int[right - left + 1];

        while(s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //走到这里相当于 tmp 数组中的元素都有序了
        //接下来将 tmp 数组中的内容拷贝到 array 中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmp[i];
        }
    }


}
